package com.lzq.leetcode.hoot100;

import java.util.*;

/**
 * 接雨水
 */
public class s42 {

    // ST算法
    public int trap(int[] height) {
        int ans = 0;
        int l = 0, r = height.length-1;
        int lh = 0, rh = height.length-1;

        while (l < r) {

            while (l < r && height[lh] <= height[rh]) {
                if (height[l] >= height[lh]) {
                    lh = l;
                } else {
                    ans += Math.min(height[lh], height[rh]) - height[l];
                }
                ++l;
            }

            while (l < r && height[rh] <= height[lh]) {
                if (height[r] >= height[rh]) {
                    rh = r;
                } else {
                    ans += Math.min(height[lh], height[rh]) - height[r];
                }
                --r;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new s42().trap(new int[]{4,2,3}));

    }
}
